package com.bobo;

import java.util.*;

/**
 * @Author: bobobo
 * @Date: 2019/9/9 18:27
 * @Version：1.0
 */
public class DivideString {

    public static void main(String[] args) {
        List<Integer> list = divide("sdgjoiejealgrtk");
        System.out.println(list);
    }


    public static List<Integer> divide(String S)
    {
        ArrayList<Integer> list = new ArrayList<>();
        // 键：字符，值：下标
        HashMap<Character, Integer> map = new HashMap<>();

        int n = S.length();

        // 第一遍循环，记录每一个字符最后出现的位置
        for (int i=0; i<n; i++)
        {
            map.put(S.charAt(i), i);
        }

        int last = -1; // 最后一次出现的位置
        char c;
        int begin = 0;

        // 第二遍循环
        for (int j=0; j<n; j++)
        {
            c = S.charAt(j);

            // 表示当前字符仅仅出现了一次
            if (map.get(c) == j && j > last)
            {
                list.add(1);
                begin = j+1;  // caedbdedda
            }
            // 表示当前字符最后出现位置，在前面字符最后出现的位置之前
            else if (map.get(c) < last)
            {
                continue;
            }
            else if (j == last)
            {
                list.add(j-begin+1); // 增加一个片段
                begin = last+1; // 这里要注意
            }
            else
            {
                last = map.get(c);
            }
        }
        return list;
    }
}
